// https://leetcode.cn/problems/binary-prefix-divisible-by-5/?envType=daily-question&envId=2025-11-27

// 算法思路总结：
// 1. 遍历数组，逐步构建二进制数并计算对5取模的结果
// 2. 利用模运算性质：(a * b + c) % m = ((a % m) * b + c) % m
// 3. 每次左移后取模，避免数值溢出
// 4. 检查模结果为0判断是否能被5整除
// 5. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) 
    {
        vector<bool> ret(nums.size());

        int x = 0;
        for (int i = 0 ; i < nums.size() ; i++) 
        {
            x = (x << 1 | nums[i]) % 5;
            ret[i] = x == 0;
        }
        return ret;
    }
};

int main()
{
    vector<int> nums1 = {0,1,1}, nums2 = {1,1,1};
    Solution sol;

    auto r1 = sol.prefixesDivBy5(nums1);
    auto r2 = sol.prefixesDivBy5(nums2);

    return 0;
}